package com.yuren.codecrushlearn.Q5100;

/**
 * Created with Intellij IDEA.
 * Description:
 * 记忆化爬楼梯
 *
 * @author Sleepy Code Tom
 * @date 2025-03-25 00:01
 */
public class Q5123 {
    private int[] mem;

    public int climbStairs(int n) {
        mem = new int[n + 1];
        return climbStairs_recur(n);
    }

    private int climbStairs_recur(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (mem[n] != 0) return mem[n];
        mem[n] = climbStairs_recur(n - 1) + climbStairs_recur(n - 2);
        return mem[n];
    }
}
